//给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 
//
// 说明：解集不能包含重复的子集。 
//
// 示例: 
//
// 输入: nums = [1,2,3]
//输出:
//[
//  [3],
//  [1],
//  [2],
//  [1,2,3],
//  [1,3],
//  [2,3],
//  [1,2],
//  []
//] 
// Related Topics 位运算 数组 回溯算法 
// 👍 732 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//Java：子集
public class P78Subsets {

    /**
     *
     * 思路： 简单的回溯算法，每次递归都保存一下结果，得到的就是子集了
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 28.98% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 81.75% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> subsets(int[] nums) {
            dfs(0, nums, new Stack<>());
            return list;
        }

        private void dfs(int start, int[] nums, Stack<Integer> path) {
            List<Integer> numList = new ArrayList<>(path);
            list.add(numList);

            for (int i = start; i < nums.length; i++) {
                path.push(nums[i]);
                dfs(i + 1, nums, path);
                path.pop();
            }

        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums = new int[]{};
        Solution solution = new P78Subsets().new Solution();
        solution.subsets(nums);
        // TO TEST
    }

}